package com.zhangxiaofanfan.hotcode.fourth.third;

/**
 * <a href="https://leetcode.cn/problems/longest-common-subsequence/description/?envType=study-plan-v2&envId=top-100-liked">1143. 最长公共子序列</a>
 *
 * @date 2024-07-13 03:14:13
 * @author zhangxiaofanfan
 */
public class HotCode094 {
    public static void main(String[] args) {
        HotCode094 hotCode = new HotCode094();
        System.out.println(hotCode.longestCommonSubsequence("abcde", "ace"));
    }

    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text2 == null || text1.isEmpty() || text2.isEmpty()) {
            throw new RuntimeException("入参不合法, 字符串长度最小为 1");
        }
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for (int index1 = 1, index2; index1 <= text1.length(); index1++) {
            for (index2 = 1; index2 <= text2.length(); index2++) {
                if (text1.charAt(index1 - 1) == text2.charAt(index2 - 1)) {
                    dp[index1][index2] = dp[index1 - 1][index2 - 1] + 1;
                } else {
                    dp[index1][index2] = Math.max(dp[index1 - 1][index2], dp[index1][index2 - 1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}